#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum {
    NPREF   = 2,    /* number of the prefix words */
    MUL     = 31,   /* multiplier for the hash value */
    NHASH   = 4093, /* size of state hash table array */
    MAXGEN  = 10000 /* maximum words generated */
};

typedef struct state state;
typedef struct suffix suffix;

struct state {      /* prefix + suffix list */
    char    *prefix[NPREF]; /* prefix words */
    suffix  *suf;           /* list of suffixes */
    state   *next;          /* next in hash table */
};

struct suffix {     /* list of suffixes */
    char    *word;          /* suffix */
    suffix  *next;          /* next in list of suffixes */
};

state   *statetab[NHASH];   /* hash table of states */
char    NONWORD[] = "\n";   /* cannot appear as readl word */

/* hash: compute hash value for array */
unsigned hash(char *s[NPREF])
{
    unsigned int    hash;
    unsigned char   *p;
    int             i;

    hash = 0;
    for (i = 0; i < NPREF; i++) {
        for (p = (unsigned char *)s[i]; *p != '\0'; p++) {
            hash = MUL*hash + *p; 
        }
    }

    return hash % NHASH;
}

/* lookup: search for prefix; create if requested.
 * returns pointers if present or created; NULL if not.
 * creation doesn't strdup so string change later.
 */
state *lookup(char *prefix[NPREF], int create)
{
    int     i, h;
    state   *sp;

    h = hash(prefix);
    for (sp = statetab[h]; sp != NULL; sp = sp->next) {
        for (i = 0; i < NPREF; i++) {
            if (strcmp(prefix[i], sp->prefix[i]) != 0)
                break;
        }
        if (i == NPREF)
            return sp;
    }

    if (create) {
        sp = (state *)malloc(sizeof(state));
        if (sp == NULL) {
            perror("malloc error");
            exit(1);
        }
        for (i = 0; i < NPREF; i++) {
            sp->prefix[i] = prefix[i];
        }
        sp->suf = NULL;
        sp->next = statetab[h];
        statetab[h] = sp;
    }

    return sp;
}

/* addsuffix: add to state. suffix must not change later */
void addsuffix(state *sp, char *suf)
{
    suffix *sufp;

    sufp = (suffix *)malloc(sizeof(suffix));
    if (sp == NULL) {
        perror("malloc error");
        exit(1);
    }

    sufp->word = suf;
    sufp->next = sp->suf;
    sp->suf = sufp;
}

/* add: add word to suffix list, update prefix */
void add(char *prefix[NPREF], char *suffix)
{
    state *sp;

    /* create if not found */
    sp = lookup(prefix, 1);
    addsuffix(sp, suffix);
    
    /* move the words down the prefix */
    memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
    prefix[NPREF-1] = suffix;
}

/* build: read input, build prefix table */
void build(char *prefix[NPREF], FILE *f)
{
    char buf[100], fmt[10];

    /* create a formate string; %s could overflow buf */
    sprintf(fmt, "%%%ds", sizeof(buf)-1);
    while (fscanf(f, fmt, buf) != EOF)
        add(prefix, strdup(buf));
}

/* generate: produce output, one word per line */
void generate(int nwords)
{
    state   *sp;
    suffix  *suf;
    char    *prefix[NPREF], *w;
    int     i, nmatch;

    /* reset initial prefix */
    for (i = 0; i < NPREF; i++) {
        prefix[i] = NONWORD;
    }

    for (i = 0; i < nwords; i++) {
        sp = lookup(prefix, 0);
        nmatch = 0;
        for (suf = sp->suf; suf != NULL; suf = suf->next) {
            if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
                w = suf->word;
        }

        if (strcmp(w, NONWORD) == 0) {
            printf("\n");
            break;
        }
        printf("%s ", w);
        memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
        prefix[NPREF-1] = w;
    }
}

/* markov main: makov-chain random text generation*/
int main(int argc, char *argv[])
{
    int     i, nwords = MAXGEN;
    char    *prefix[NPREF];

    for (i = 0; i < NPREF; i++) {
        prefix[i] = NONWORD;
    }

    build(prefix, stdin);
    add(prefix, NONWORD);
    generate(nwords);

    return 0;
}
